package com.practice.tree;

import com.practice.util.BinaryTree;
import com.practice.util.BinaryTreeNode;

/**
 * Find largest BST in a binary tree (may not including all descendants). 
 */
public class LargestIncompleteBST {
	public int find(BinaryTree tree) {
		Result r = find(tree.getRoot());
		return r.maxBST;
	}
	
	public Result find(BinaryTreeNode node) {
		return find(node, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}
	
	public Result find(BinaryTreeNode node, int min, int max) {
		if (node == null) return new Result(0, 0);
		
		boolean isBST = node.value()>min && node.value()<max;
		Result left = isBST? find(node.left(), min, node.value()) : find(node.left());
		Result right = isBST? find(node.right(), node.value(), max) : find(node.right());
		
		int total = 1 + left.nodes + right.nodes;
		return new Result(isBST? total : 0, Math.max(total, Math.max(left.maxBST, right.maxBST)));
	}
	
	private class Result {
		int		nodes;
		int		maxBST; 	
		
		public Result(int nodes, int maxBST) {
			this.nodes = nodes;
			this.maxBST = maxBST;
		}
	}
}
